package algorithms

import (
	"Algorithms/datastruct"
)

//定义邻接表数据结构（graph）来表示拓扑，时间复杂度O(v+e)
//应用，利用局部顺序来计算全局顺序
//kahn算法
func TopoSortKahn(g datastruct.Graph) []int {
	//统计入度
	inDegree := make([]int, g.V)
	for i := 0; i < g.V; i++ {
		for j := 0; j < len(g.Adj[i]); j++ {
			w := g.Adj[i][j]
			inDegree[w]++
		}
	}
	//添加排序队列
	q := make([]int, 0)
	//添加起始点，也就是入度为0的点
	for i := 0; i < g.V; i++ {
		if inDegree[i] == 0 {
			q = append(q, i)
		}
	}
	res := make([]int, 0)
	//给起始节点后续节点排序
	for len(q) != 0 {
		i := q[len(q)-1]
		q = q[:len(q)-1]
		res = append(res, i)
		for j := 0; j < len(g.Adj[i]); j++ {
			k := g.Adj[i][j]
			inDegree[k]--
			if inDegree[k] == 0 {
				q = append(q, k)
			}
		}
	}
	return res
}

//dfs算法
func TopoSortDFS(g datastruct.Graph) []int {
	//需要用到逆邻接表，因为dfs最后找到的是出度为0的，需要转换为入度
	inverseAdj:=make([][]int,g.V)
	for i:=0;i<g.V;i++{
		inverseAdj[i]=make([]int,0)
	}
	for i:=0;i<g.V;i++{
		for j:=0;j< len(g.Adj[i]);j++{
			w:=g.Adj[i][j]
			inverseAdj[w]=append(inverseAdj[w], i)
		}
	}
	visited := make([]bool, g.V)
	res:=make([]int,0)
	var dfs func(int)
	dfs = func(vertex int) {
		for i := 0; i < len(inverseAdj[vertex]); i++ {
			w:=inverseAdj[vertex][i]
			if !visited[w]{
				visited[w]=true
				dfs(w)
			}
		}
		//最后打印自己，先打印末尾（也就是正向图的开头）
		res=append(res, vertex)
	}
	for i := 0; i < len(inverseAdj); i++ {
		if !visited[i] {
			visited[i] = true
			dfs(i)
		}
	}
	return res
}
